package com.lw.leetcode.arr.c;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 1289. 下降路径最小和  II
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/30 14:36
 */
public class MinFallingPathSum {

    public static void main(String[] args) {
        MinFallingPathSum test = new MinFallingPathSum();
        int[][] arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int i = test.minFallingPathSum(arr);
        System.out.println(i);
    }

    public int minFallingPathSum(int[][] grid) {
        int length = grid.length;
        int av1 = 0;
        int bv1 = 0;
        int ai1 = -1;
        int av2;
        int bv2;
        int ai2;
        for (int i = 0; i < length; i++) {
            int[] items = grid[i];
            av2 = Integer.MAX_VALUE;
            bv2 = Integer.MAX_VALUE;
            ai2 = 0;
            for (int j = 0; j < length; j++) {
                if (ai1 == j) {
                    items[j] += bv1;
                } else {
                    items[j] += av1;
                }
                int item = items[j];
                if (item <= av2) {
                    bv2 = av2;
                    av2 = item;
                    ai2 = j;
                } else if (item < bv2) {
                    bv2 = item;
                }
            }
            av1 = av2;
            bv1 = bv2;
            ai1 = ai2;
        }
        return av1;
    }

}
